/*
Given a n*n grid map that is parallel with x, y axis, the down left point is (0,0),the up right point is (n,n). Given n rectangles, the down left point and up right point are (x1,y1)(x1',y1'),..., (xn,yn)(xn',yn'). xn,yn,xn',yn',n are non-negative integers, and all rectangles are parallel with axis. Design a query which return, for a specific grid unit (x,y)(x+1,y+1), how many rectangles cover it? Minimize the time complexity of the query and the pre-processing. 1<n<1000
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class rect_t 
{
public:
    rect_t(int a, int b, int c, int d): x1(a), y1(b), x2(c), y2(d) {}
    int x1, y1, x2, y2;
};

bool myComp(rect_t lhs, rect_t rhs)
{
    if (lhs.x1 < rhs.x1) 
        return true;
    else if (lhs.x1 > rhs.x1) 
        return false;

    if (lhs.y1 < rhs.y1) 
        return true; 
    else if (lhs.y1 > rhs.y1) 
	return false;

    if (lhs.x2 < rhs.x2) 
        return true;
    else if (lhs.x2 > rhs.x2)
	return false;

    if (lhs.y2 < rhs.y2) 
        return true;
    else if (lhs.y2 > rhs.y2)
        return false;

    return false;
}



int main(int argc, char **argv)
{
    vector<rect_t> rectVec;
    rectVec.push_back(rect_t(1,1,7,8));
    rectVec.push_back(rect_t(2,2,7,6));
    rectVec.push_back(rect_t(1,3,8,9));
    rectVec.push_back(rect_t(3,4,7,8));
    rectVec.push_back(rect_t(4,5,7,9));
    rectVec.push_back(rect_t(3,5,12,17));
    rectVec.push_back(rect_t(2,4,45,78));
    sort(rectVec.begin(), rectVec.end(), myComp);
    for (int i = 0; i < rectVec.size(); i++) 
        cout << rectVec[i].x1 << " " << rectVec[i].y1 << " " << rectVec[i].x2 << " " << rectVec[i].y2 << endl;
}
